#include <iostream>
#include "../head/TreeNode.h"

using namespace std;


// 437. Path Sum III
// 时间复杂度: O(n), n为树的节点个数
// 空间复杂度: O(h), h为树的高度
class Solution {
public:
	// 在以root为根节点的二叉树中,寻找和为sum的路径,返回这样的路径个数
	int pathSum(TreeNode* root, int sum) {
		if(root == NULL) return 0;
		
		return findPath(root, sum) + pathSum(root->left, sum) + pathSum(root->right, sum);	
    }
private:

    // 在以node为根节点的二叉树中,寻找包含node的路径,和为sum
    // 返回这样的路径个数
    int findPath(TreeNode* node, int num){

        if(node == NULL)
            return 0;

        int res = 0;
        if(node->val == num)
            res += 1;

        res += findPath(node->left , num - node->val);
        res += findPath(node->right , num - node->val);

        return res;
    }
};
